/*
 * File: Scatter.c
 *
 * Integrantes:
 * 05-37840 Jormar Arellano
 * 05-38163 Sabrina Fernández
 */

#include "Scatter.h"
#include "arraylist.h"
#include "util.h"
#include "LocalSearch.h"

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

void scatter_defaults(){
    scatter_population_size = 15;
    scatter_initial_k = 100;
    scatter_b = 5;
    scatter_d = 5;
    scatter_imp_method = apply_local_search;
    scatter_verbose = 0;
}

Configuration *newConfiguration(){
    Configuration *c = malloc(sizeof(Configuration));
    c->partition = arraylist_new(0);
    c->isNew = 1;
    c->numConflicts = 0;
    return c;
}

void freeConfiguration(Configuration *c){
    freePartition(c->partition);
    free(c);
}

int compareConfigurationByVertexId(ArrayListValue v1, ArrayListValue v2){
    int i, j;
    ArrayList *va = ((Configuration*)v1)->partition;
    ArrayList *vb = ((Configuration*)v2)->partition;
    ArrayList *pva, *pvb;

    if(va->length != vb->length) return 1;

    for(i=0; i<va->length; i++){
        pva = va->data[i];
        pvb = vb->data[i];
        if(pva->length != pvb->length) return 1;
        for(j=0; j<pva->length; j++){
            if(arraylist_index_of(pvb, compareVertexById, pva->data[j])<0){
                return 1;
            }
        }
    }

    return 0;
}

int compareConfigurationByBest(ArrayListValue v1, ArrayListValue v2){
    Configuration *va = v1;
    Configuration *vb = v2;

    if(va->numConflicts < vb->numConflicts) return -1;
    if(va->numConflicts > vb->numConflicts) return 1;
    return 0;
}

int compareConfigurationByDiverse(ArrayListValue v1, ArrayListValue v2){
    ArrayList *va = ((Configuration*)v1)->partition;
    ArrayList *vb = ((Configuration*)v2)->partition;
    ArrayList *aux;
    int i;
    int maxa, maxb, mina, minb;
    int diva, divb;

    for(i=0, mina=INT_MAX, maxa=0; i<va->length; i++){
        aux = va->data[i];
        if(aux->length<mina) mina = aux->length;
        if(aux->length>maxa) maxa = aux->length;
    }
    diva = maxa-mina;

    for(i=0, minb=INT_MAX, maxb=0; i<vb->length; i++){
        aux = vb->data[i];
        if(aux->length<minb) minb = aux->length;
        if(aux->length>maxb) maxb = aux->length;
    }
    divb = maxb-minb;
    if(diva < divb) return -1;
    if(diva > divb) return 1;

    return 0;
}

void paintGraphfromPartition(Graph *graph, ArrayList *Pi){
    int i, j, color;
    ArrayList *auxL;

    // Quitamos todos los colores actuales del grafo
    discolorGraph(graph);

    for(i=0; i<Pi->length; i++){
        auxL = Pi->data[i];
        color = i+1;
        for(j=0; j<auxL->length; j++){
            setColor(graph, auxL->data[j], color);
        }
    }
}

void dummyPaintGraphFromPartition(Graph *graph, ArrayList *Pi){
    int i, j, color;
    ArrayList *auxL;
    Vertex *v;

    // Quitamos todos los colores actuales del grafo
    discolorGraph(graph);

    for(i=0; i<Pi->length; i++){
        auxL = Pi->data[i];
        color = i+1;

        for(j=0; j<auxL->length; j++){
            v = auxL->data[j];
            v->color = color;
        }
    }
}

ArrayList *copyPartition(ArrayList *P){
    int i, j;
    ArrayList *Pi, *auxL;

    Pi = arraylist_new(0);
    for(i=0; i<P->length; i++){
        auxL = P->data[i];
        arraylist_append(Pi, arraylist_new(0));

        for(j=0; j<auxL->length; j++){
            arraylist_append(Pi->data[i], auxL->data[j]);
        }
    }
    return Pi;
}

void freePartition(ArrayList *P){
    int i;
    if(P){
        for(i=0; i<P->length; i++){
            arraylist_free(P->data[i]);
        }
        arraylist_free(P);
    }
}

int calculePartitionConflicts(Graph *graph, ArrayList *P){
    int i, j;
    int resp = 0;
    Vertex *v;
    ArrayList *auxP;

    // Pintamos el grafo de forma ligera
    dummyPaintGraphFromPartition(graph, P);

    for(i=0; i<P->length; i++){
        auxP = P->data[i];

        for(j=0; j<auxP->length; j++){
            v = auxP->data[j];

            // verifica si tiene coflictos
            if(vertexHasConflict(v, i+1)){
                resp++;
            }
        }
    }

    return resp/2;
}

ArrayList *diversification_method(const Graph *graph) {
	int i, j;
	ArrayList *A=NULL, *Vi, *V, *neighbors;
	Vertex *v, *v2;

	V = arraylist_copy(graph->vertex);
    Vi = arraylist_new(0);

    // Inicializamos variables especiales
    for(i=0; i<V->length; i++){
        v = V->data[i];
        v->_scatter_vi = 0;
    }

	for (i=0; i<scatter_initial_k && V->length; i++) {
		A = arraylist_new(0);
        arraylist_append(Vi, arraylist_new(0));

		while (V->length) {
			v = V->data[ rand()%V->length ];
			arraylist_remove(V, arraylist_index_of(V, compareVertexById, v));
            v->_scatter_vi = 1;
            arraylist_append(Vi->data[i], v);

            neighbors = v->neighbors;
            for(j=0; j<neighbors->length; j++){
                v = neighbors->data[j];

                if(
                        arraylist_index_of(A, compareVertexById, v)<0
                        && !v->_scatter_vi
                        ){
                    arraylist_append(A, v);
                }
                arraylist_remove(V,
                        arraylist_index_of(V, compareVertexById, v));

            }

		}
        arraylist_free(V);
        V = A;
	}

	// Put each v en W in a color class such as it minimizes
	// the conflicts over the graph 
    int minColor, color, min, count;
    for(i=0; i<V->length; i++){
        v = V->data[i];

        for(color=0, minColor=color, min=INT_MAX; color<Vi->length; color++){
            // Cuento cuantos vecinos estan en este color
            for(j=0, count=0; j<v->neighbors->length; j++){
                v2 = v->neighbors->data[j];
                if(arraylist_index_of(Vi->data[color], compareVertexById, v2)>=0){
                    count++;
                }
            }

            if(count<min){
                min = count;
                minColor = color;
            }
        }

        // DEBUG
        // printf("Asignando %d => %d, con %d conflictos\n", v->id, minColor, min);

        // Asigno el vertice al color que da menos conflictos
        arraylist_append(Vi->data[minColor], v);
    }

    // Liberamos recursos
    if(A) arraylist_free(A);

	return Vi;
}

ArrayList *scatter_subsetGeneration(ArrayList *P){
    int i, j;
    Configuration *ca, *cb;
    ArrayList *resp, *aux;

    resp = arraylist_new(0);
    for(i=0; i<P->length; i++){
        ca = P->data[i];
        for(j=i+1; j<P->length; j++){
            cb = P->data[j];

            // Al menos una de las configuraciones es nueva
            if(ca->isNew || cb->isNew){
                aux = arraylist_new(2);
                arraylist_append(aux, ca);
                arraylist_append(aux, cb);
                arraylist_append(resp, aux);
            }
        }
    }

    // Ninguna de las configuraciones es nueva
    for(i=0; i<P->length; i++){
        ca = P->data[i];
        ca->isNew = 0;
    }

    return resp;
}

void scatter_freeSubets(ArrayList *subset){
    int i;
    for(i=0; i<subset->length; i++){
        arraylist_free(subset->data[i]);
    }
    arraylist_free(subset);
}

ArrayList *choosePartitionMaxCard(ArrayList *P){
    int i, j, length, maxLength;
    ArrayList *aux, *max;
    Vertex *v;

    maxLength = 0;
    max = P->data[0];
    for(i=0; i<P->length; i++){
        aux = P->data[i];

        length = 0;
        for(j=0; j<aux->length; j++){
            v = aux->data[j];

            if(v->_scatter_confCombFlag==0){
                length++;
            }
        }

        if(length>maxLength){
            maxLength = length;
            max = aux;
        }
    }

    return max;
}

Configuration *scatter_confCombination(ArrayList *P){
    int i, j, k;
    int totalVertices, countV, choose;
    ArrayList *aux, *Pi;
    Vertex *v;
    Configuration *s;

    // Inicialize variables
    k=0;
    for(i=0; i<P->length; i++){
        aux = P->data[i];
        countV = 0;
        for(j=0; j<aux->length; j++){
            v = aux->data[j];
            v->_scatter_confCombFlag = 0;
            countV = 0;
        }
        totalVertices = countV;
        k += aux->length;
    }
    k /= 2;

    s = newConfiguration();
    s->partition = arraylist_new(0);
    for(
            i=0, countV=0, choose = 0;
            i<k && countV<totalVertices;
            i++, choose = (choose+1)%P->length)
    {
        // Tomamos un bloque de mayor cardinalidad
        aux = choosePartitionMaxCard(P->data[choose]);
        Pi = arraylist_new(0);

        for(j=0; j<aux->length; j++){
            v = aux->data[j];

            // Tomamos los vertices sin considerar
            if(v->_scatter_confCombFlag==0){
                arraylist_append(Pi, v);
                v->_scatter_confCombFlag = 1;
            }
        }

        arraylist_append(s->partition, Pi);
    }

    return s;
}

long scatter_evaluation(Configuration *c){
    return c->numConflicts;
}

Graph *scatter(Graph *graph) {
    int i;
	ArrayList *P, *Pi; // Population
    ArrayList *refSet;
    int newSolutions;
    ArrayList *subsets, *set;
    Configuration *c;

    // Disminuimos el verbose de local search
    ls_verbose--;
    ls_verbose--;

    if(scatter_verbose>0){
        printf("    + Generando poblacion inicial\n");
    }

	P = arraylist_new(0);
    while(P->length < scatter_population_size){
        Pi = diversification_method(graph);

        // Pintamos el grafo
        paintGraphfromPartition(graph, Pi);

        // NOTA: ya no necesitamos Pi
        arraylist_free(Pi);

        // Mejoramos la solucion actual
        graph = scatter_imp_method(graph);
        removeDeadColors(graph);

        // Creamos la particion a evaluar
        Configuration *conf = newConfiguration();
        conf->partition = graph->Vcolors;

        if(arraylist_index_of(P, compareConfigurationByVertexId, conf)<0){
            // Hacemos una copia de la particion de colores
            conf->partition = copyPartition(graph->Vcolors);
            arraylist_append(P, conf);

            if(scatter_verbose>1)
                printf("        + Se agrego un nuevo individuo a la poblacion\n");
        } else {
            if(scatter_verbose>1)
                printf("        + YA estaba\n");

            // No se usara la configuration creada
            conf->partition = NULL;
            freeConfiguration(conf);
        }
    }

    if(_steps) waitStep();

    if(scatter_verbose>0){
        printf("    + Armando el conjunto de referencia (%d mejores, %d diversos)\n",
                scatter_b, scatter_d);
    }

    // Actualizamos el numero de conflictos de las configs
    for(i=0; i<P->length; i++){
        c = P->data[i];
        c->numConflicts =
            calculePartitionConflicts(graph, c->partition);
    }

    // Creamos el conjunto de referencia
    refSet = arraylist_new(0);

    arraylist_sort(P, compareConfigurationByBest);
    for(i=0; i<scatter_b && i<P->length; i++){
        arraylist_append(refSet, P->data[i]);
    }

    arraylist_sort(P, compareConfigurationByDiverse);
    for(i=0; i<scatter_d && i<P->length; i++){
        arraylist_append(refSet, P->data[i]);
    }

    if(scatter_verbose>1){
        printf("    + %d elem. en conjunto de referencia.\n", refSet->length);
    }

    // mantenemos el conjunto ordenado por soluciones
    arraylist_sort(refSet, compareConfigurationByBest);

    newSolutions = 1;
    while(newSolutions){
        subsets = scatter_subsetGeneration(P);
        newSolutions = 0;

        for(i=0; i<subsets->length; i++){
            set = subsets->data[i];
            c = scatter_confCombination(set);
            c->numConflicts =
                calculePartitionConflicts(graph, c->partition);

            if(arraylist_index_of(refSet, compareConfigurationByVertexId, c)<0
                    && scatter_evaluation(c)<scatter_evaluation(refSet->data[0])){
                arraylist_sort(refSet, compareConfigurationByBest);
                arraylist_insert(refSet, 0, c);
                arraylist_remove(refSet, refSet->length-1);
                newSolutions = 1;

                if(scatter_verbose>1)
                    printf("        + Nueva solucion\n");
            } else {
                // liberamos memoria de configuracion no usada
                freeConfiguration(c);
            }
        }
    }

    // Pintamos el grafo con la mejor coloracion
    paintGraphfromPartition(graph,
            ((Configuration *)refSet->data[0])->partition);

	return graph;
}

